class Solution:
    def minTaps(self, n: int, ranges: [int]) -> int:
        prev = [x for x in range(n + 1)]
        for i in range(n + 1):
            l = max(i - ranges[i], 0)
            r = min(i + ranges[i], n)
            prev[r] = min(prev[r], l)

        BIG = 0xffff
        dp = [0] + [BIG] * n
        for i in range(1, n + 1):
            # 第i个区域已经覆盖, 还剩(0, i-1)需要覆盖
            for j in range(prev[i], i):
                if dp[j] != BIG:
                    # 可以覆盖到i的最少区间数
                    dp[i] = min(dp[i], dp[j] + 1)

        return -1 if dp[n] == BIG else dp[n]
